DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2024.24

The Worst-Case Complexity of Symmetric Strategy Improvement

Authors: Tom van Dijk, Georg Loho, and Matthew T. Maat

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract

Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usual well-known strategy improvement algorithm, it iterates over strategies of both players simultaneously. The symmetric version solves the known worst-case examples for strategy improvement quickly, however its worst-case complexity remained open. We present a class of worst-case examples for symmetric strategy improvement on which this symmetric version also takes exponentially many steps. Remarkably, our examples exhibit this behaviour for any choice of improvement rule, which is in contrast to classical strategy improvement where hard instances are usually hand-crafted for a specific improvement rule. We present a generalized version of symmetric strategy iteration depending less rigidly on the interplay of the strategies of both players. However, it turns out it has the same shortcomings.

Cite as

Tom van Dijk, Georg Loho, and Matthew T. Maat. The Worst-Case Complexity of Symmetric Strategy Improvement. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vandijk_et_al:LIPIcs.CSL.2024.24,
  author =	{van Dijk, Tom and Loho, Georg and Maat, Matthew T.},
  title =	{{The Worst-Case Complexity of Symmetric Strategy Improvement}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.24},
  URN =		{urn:nbn:de:0030-drops-196672},
  doi =		{10.4230/LIPIcs.CSL.2024.24},
  annote =	{Keywords: Parity game, Mean payoff game, Symmetric strategy improvement, Strategy improvement, Worst-case complexity}
}

Search Results

Documents authored by Maat, Matthew T.

The Worst-Case Complexity of Symmetric Strategy Improvement

Abstract

Cite as

Thanks for your feedback!

Could not send message